package org.basis.algorithm.tree;

import org.basis.algorithm.tree.common.TreeNode;

import java.util.LinkedList;

/**
 * 树的宽度优先遍历
 *
 * @author Mr_wenpan@163.com 2021/12/12 18:54
 */
public class BreadthFirstTraverse {

    public static void main(String[] args) {

    }

    /**
     * 树的宽度优先遍历
     */
    public static void widthFirst(TreeNode<Integer> head) {
        if (head == null) {
            return;
        }
        // 准备一个队列
        LinkedList<TreeNode<Integer>> queue = new LinkedList<>();
        TreeNode<Integer> cur = head;
        queue.add(cur);
        while (!queue.isEmpty()) {
            // 从队列里弹出就打印
            TreeNode<Integer> pollFirst = queue.pollFirst();
            System.out.print(pollFirst.data + "   ");
            // 左右孩子入队列
            if (pollFirst.left != null) {
                queue.addLast(pollFirst.left);
            }
            if (pollFirst.right != null) {
                queue.addLast(pollFirst.right);
            }
        }
    }


}
